package library;

import java.util.List;

/**
 * BellmanFord is a fastest path algorithm that can detect negative cycles.
 * It cannot complete the search if they are detected, but it can detect them.
 * @author ekulcyk
 *
 */
public class BellmanFord {
	
	public int BellmanFord(Node source, Node destination, Node[] nodes, List<Edge> edges){
		for (Node n: nodes){
			if (n==source) n.distance = 0;
			else n.distance = Integer.MAX_VALUE;
			n.predecessor=null;
		}
		for (Node n: nodes)
			for (Edge e: n.edges)
				if (e.source.distance + e.weight < e.destination.distance){
					e.destination.distance = e.source.distance + e.weight;
					e.destination.predecessor = e.source;
				}
		for (Edge e : edges)
			if (e.source.distance + e.weight < e.destination.distance)
				System.out.println("Negative Cycle");
		return destination.distance;
	}
	class Node{
		Node predecessor;
		int distance;
		List<Edge> edges;
	}
	class Edge{
		int weight;
		Node source,destination;
	}
}
